package 排序.交换排序;
public class QuickSort {
    /**
     * 快速排序
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(logN)
     */
    public static void quickSork(int[] array){
        quick(array,0,array.length-1);
    }
    public static void quick(int[] array,int start,int end){
        if(start>=end){
            return;
        }

        int pivot=partition(array,start,end);

        quick(array,start,pivot-1);

        quick(array,pivot+1,end);

    }

    private static int partition(int[] array, int left, int right) {
        /**
         * Hoare
         *
         */
        int tmp=array[left];

        int Index=left;

        while(left<right){
            while(left<right && array[right]>=tmp){
                right--;
            }
            while(left<right && array[left]<=tmp){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,Index);
        return left;
    }
    public static void swap(int[] array,int A,int B){
        int temp=array[A];
        array[A]=array[B];
        array[B]=temp;
    }
}
